package com.hw2;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;


public class PatternMatching {

	 //relative coords of neighbor cells to given cell
    int[] rN={-1,-1,-1,0,0,1,1,1};
    int[] cN={-1,0,1,-1,1,-1,0,1};
    int Row,Col;
    
    
    public PatternMatching(char[][] C, char[] P){
        Row=C.length;
        Col=C[0].length;
    }
    
    public PatternMatching(){
    
    }
    
    boolean isCoordValid(int r,int c){
        if(r<Row && r>=0 && c<Col && c>=0)
            return true;
        return false;
    }
    
    private String getStringfromList(List<CharP> l){
    	String s="";
    	for (CharP charP : l) {
			s=s+charP.getC();
		}
    	return s;
    }
    public Set<String> checkPattern(char[][] C){
    	//initial conditions
    	
    	//get trie
    	Trie trie=new Trie();
    	String path="/home/arjun/workspace/interview/src/wordsEn.txt";
		trie.readDictionary(path);
		
		Map<Character,CharP> map=trie.root;
		List<CharP> P=new ArrayList<CharP>();
		Row=C.length;
        Col=C[0].length;
        boolean[][] visited = new boolean[Row][Col];
        Set<String> set=new HashSet<String>();
        //end initial conditions
        
        for (Entry<Character, CharP> entry : map.entrySet()){
        	P.add(entry.getValue());
        	Set<String> l = checkPattern(C,P,visited);
        	set.addAll(l);
        	P.remove(entry.getValue());
        }

        return set;

    }
    private Set<String> checkPattern(char[][] C, List<CharP> P,boolean[][] visited){
       
        Set<String> set=new HashSet<String>();
        for(int i=0;i<Row;i++){
            for(int j=0;j<Col;j++){
                visited[i][j]=true;
                checkPattern(C,P,visited,set,0,i,j);
                visited[i][j]=false;
            }
        }
        return set;
    }
    
    
    private void checkPattern(char[][] C,List<CharP> P,boolean[][] visited, Set<String> set,int index,int r,int c){
        if(P.get(index).getC()==C[r][c] && P.get(index).isWord){
        	set.add(getStringfromList(P));	
        }
    	
        if(P.get(index).getC()==C[r][c]){
        	Map<Character,CharP> map=P.get(index).getChildren();
        	for (Entry<Character, CharP> entry : map.entrySet()){
            	P.add(entry.getValue());
            	for(int i=0;i<8;i++){
                    int nr = r+rN[i];
                    int nc = c+cN[i];
                    if(isCoordValid(nr,nc) && !visited[nr][nc]){
                        visited[nr][nc]=true;
                        checkPattern(C,P,visited,set,index+1,nr,nc);
                        visited[nr][nc]=false;
                    }
                }
            	P.remove(entry.getValue());
            }
        }
    }
}

